package swardToOffer.struct_1_arr;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @Author ChanZany
 * @Date 2021/5/24 15:25
 * @Version 1.0
 面试题41：数据流中的中位数
 题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么
 中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，
 那么中位数就是所有数值排序之后中间两个数的平均值。
    例如，
    [2,3,4] 的中位数是 3
    [2,3] 的中位数是 (2 + 3) / 2 = 2.5
    设计一个支持以下两种操作的数据结构：
    void addNum(int num) - 从数据流中添加一个整数到数据结构中。
    double findMedian() - 返回目前所有元素的中位数。
解法：
建立一个 小顶堆 AA 和 大顶堆 BB ，各保存列表的一半元素，且规定：
A 保存 较大 的一半，长度为 N/2（ N 为偶数）或 N+1/2（N为奇数）；
B 保存 较小 的一半，长度为 N/2（ N 为偶数）或 N-1/2（N为奇数）；
为保证A B所保存的元素个数均衡，且保证AB之间有序（A中最小元素>=B的最大元素），以下面的方式进行添加：
1. 当A.size! = B.size,则向B中添加元素  A.add(ele) B.add(A.poll);
2. 当A.size == B.size,则向A中添加元素  B.add(ele) A.add(B.poll)
随后，中位数可仅根据 A, B 的堆顶元素计算得到。
 */

class MedianFinder {
    Queue<Integer> A,B;
    public MedianFinder() {
        A = new PriorityQueue<>();//小顶堆，保存较大的一半，堆顶为A中最小元素
        B = new PriorityQueue<>(Comparator.reverseOrder());//大顶堆，保存较小的一半，堆顶为B中最大元素
    }

    public void addNum(int num) {
        if (A.size()==B.size()) {
            B.add(num);
            A.add(B.poll());
        }
        else {
            A.add(num);
            B.add(A.poll());
        }
    }

    public double findMedian() {
        return A.size()!=B.size()?A.peek():(A.peek()+B.peek())/2.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
public class StreamMedian {
}
